// https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return create(nums, 0, nums.size() - 1);
    }

    TreeNode* create(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* head = new TreeNode(nums[mid]);
        head->left = create(nums, left, mid - 1);
        head->right = create(nums, mid + 1, right);
        return head;
    }



    void show(TreeNode* head) {
        if (head) {
            show(head->left);
            cout << head->val << ",";
            show(head->right);
        }
    }

};


int main() {
    vector<int> nums = { -10,-3,0,5,9,10,11,12 };
    Solution so;
    auto res = so.sortedArrayToBST(nums);
    so.show(res);
    return 0;
}
